"""
4.寻找两个正序数组的中位数
https://leetcode-cn.com/problems/median-of-two-sorted-arrays

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例1:
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例2:
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示:
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6

进阶：
你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
"""
class Solution:
  """
  中位数可以这样理解：
    保留 最小的 (len+1)/2 个元素后的，或者说排除掉最大的 (len-1)/2 个元素后的 最大的元素值 或 最大的2个元素值的平均值
  
  对于两个正序数组 nums1 与 nums2:
    如果 nums1[i] > num2[j]:
       num1[i:] 任一元素 一定比 nums1[:i] 与 nums2[:j] 的任一元素 大
      设 nums 为 合并 nums1 与 nums2 后的有序列表，则 nums1[i:] 一定属于 nums[i+j:] 中的一部分
    
    故，我们使得 i + j == (len(nums) + 1) / 2:
      如果 nums1[i] > nums2[j]:
        使得 nums1 = nums1[:i] (即排除掉 nums1[i:])
      反之亦然
      进入下次迭代
      如此循环，使得 len(nums1) + len(nums2) == (len(nums) + 1) / 2
      最后取出 最大的元素值 或 最大的2个元素值的平均值 为结果值
      注意: 为了保证不管情况如何，每次迭代排除的数量足够多，应尽可能使得 len(nums1) - i == len(nums2) - j
  """
  def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
    n = len(nums1) + len(nums2) # 总长度
    m = n // 2 + 1 # 需要保留的长度
    i1 = len(nums1) # nums1的结束索引(保留的个数)
    i2 = len(nums2) # nums2的结束索引(保留的个数)
    # 迭代排除
    while i1 + i2 > m:
      if i1 == 0:
        i2 = m
      elif i2 == 0:
        i1 = m
      else:
        x = (i1 + i2 - m + 1) // 2 # 可以排除的元素个数
        if i1 <= x:
          x1 = 0
          x2 = m - 1
        elif i2 <= x:
          x1 = m - 1
          x2 = 0
        else:
          x1 = i1 - x
          x2 = i2 - x
        if nums1[x1] > nums2[x2]:
          i1 = x1
        else:
          i2 = x2
    # 迭代结束，取出最大元素值或最大的2个元素的平均作为结果值
    c =  m + m - n # 需要取出的最大个元素的个数
    t = 0
    i1 -= 1
    i2 -= 1
    for _ in range(c):
      if i1 < 0:
        t += nums2[i2]
        i2 -= 1
      elif i2 < 0:
        t += nums1[i1]
        i1 -= 1
      elif nums1[i1] > nums2[i2]:
        t += nums1[i1]
        i1 -= 1
      else:
        t += nums2[i2]
        i2 -= 1
    return t / c
